
import java.util.*;

import static java.lang.Math.abs;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
//给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
/*
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        ListNode bs = null;
        ListNode be = null;

        ListNode as = null;
        ListNode ae = null;

        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                }
            } else {
                if (bs == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        if (bs == null) {
            return as;
        }
        be.next = as;
        if(as != null){
            ae.next = null;
        }
        return bs;
    }
}*/
//相交链表
/*
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode hA1 = headA;
        ListNode hB1 = headB;
        int coA = 0;
        int coB = 0;
        while(hA1 != null){
            coA++;
            hA1 = hA1.next;
        }
        while (hB1 !=null){
            coB++;
            hB1 = hB1.next;
        }
        hA1 = headA;
        hB1 = headB;
        for (int i = 0; i<abs(coA-coB);i++){
            if (coA>coB){
                hA1 = hA1.next;
            }
            if (coB>coA) {
                hB1 = hB1.next;
            }
        }
        while (hA1 != hB1){
            hA1 = hA1.next;
            hB1 = hB1.next;
        }
        if (hA1 == null) {
            return null;
        }
        return hA1;
    }
}*/
//环形链表

/*
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;

    }
}*/
//环形链表 II
/*
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next ==null){
            return null;
        }
        slow = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
*/
